#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:

    int getKthMagicNumber(int k) {
        int* dp = new int[k];
        dp[0] = 1;
        int p[3] = { 0,0,0 };
        long v[3];
        for (int index = 1; index < k; ++index) {
            v[0] = dp[p[0]] * 3;
            v[1] = dp[p[1]] * 5;
            v[2] = dp[p[2]] * 7;
            dp[index] = min(min(v[0], v[1]), v[2]);
            for (int i = 0; i < 3; ++i) {
                if (v[i] == dp[index])
                    ++p[i];
            }
        }
        return dp[k - 1];
    }
};